/*
 Project : calculator
 Version : 0.1
 Created : seonggwang
 Describe: This calculator is first step for my project's graph program.
 Date    : 2011. 05. 08. Sunday (Writen)
           2011. 05. 05. Thursday (Created)
 */

#include <iostream>
#include <string>
#include <vector>
#include <list>
using namespace std;

int convInt(const char a)
{
	return a-'0';
}

inline bool isDigit(const char a)
{
    return ('9'>=a && '0'<=a);
}

inline bool isDot(const char a)
{
    return a == '.';
}

inline bool isAlphabet(const char a)
{
    return ('A' <= a && 'Z' >= a) || ('a' <= a && 'z' >= a);
}

bool isDigitOrDotOrAlphabet(const char a)
{
	return isDigit(a) || isDot(a) || isAlphabet(a);
}

int inputPriority(char c)
{
    switch (c) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
        case '%':
            return 3;
        case '^':
            return 6;
        case '(':
            return 9;
        case ')':
            return 0;
        default:
        {
            if(isDigitOrDotOrAlphabet(c))
                return 7;
            else
                return 0xFF;
        }
    }
}
 
int stackPriority(char c)
{
    switch (c) {
        case '+':
        case '-':
            return 2;
        case '*':
        case '/':
        case '%':
            return 4;
        case '^':
            return 5;
        case '(':
            return 0;
        default:
        {
            if(isDigitOrDotOrAlphabet(c))
                return 8;
            else
                return 0xFF;
        }
    }
}

void replace(std::string& str, const std::string& find, const std::string& replace)
{
	size_t i = 0;
	while ((i = str.find(find)) != std::string::npos)
		str.replace(i, find.size(), replace);
}

void postFix(const std::string& expression, std::string& out)
{
    std::string exprCopy = '('+ expression + "))";
    replace(exprCopy, "(+","(");
    replace(exprCopy, "(-","(0-");
    
    std::vector<char> stack;
    stack.push_back('(');
    
    string func;

    for (string::iterator it = exprCopy.begin();
         it!=exprCopy.end(); ) {
        func.push_back(*it);
        
        cout<<func<<endl;
        
        // TODO: Check the expression. (no pair paren, input error, etc..)
        
        while (inputPriority(*it) < stackPriority(stack.back())) {
            out.push_back(stack.back());
            stack.pop_back();
            
            if (inputPriority(*it)<=6) {
                out.push_back(' ');
                func.clear();
            }
            else {
            }
        }

        if (inputPriority(*it) != stackPriority(stack.back()))
            stack.push_back(*it);
        else
            stack.pop_back();

        it++;
    }
    
}

int main(int agvc, char** agvr)
{    
    string expression="(-1^2^3^4)";
    string postExpression;

//    while(1)
    {
//        getline(cin, expression);
        postFix(expression, postExpression);
        expression.clear();
        cout<<postExpression<<endl;
        postExpression.clear();
    }
    
	system("pause");

	return 0;
}

